package com.cuz.daileetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author cuzz
 * @version 1.0
 * @description: 15. 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 示例 2：
 * <p>
 * 输入：nums = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：nums = [0]
 * 输出：[]
 * @date 22:44 2021/9/23
 **/
public class Day6 {

    /**
     * @author cuzz
     * @description 排序加双指针
     * <p>
     * 为什么使用双指针
     * 头指针+尾指针之和看作一个值A，中间指针的值看做另外一个值B
     * A+B=0 A增加B减小 将数组排序 根据头值+中值+尾值的大小 去改变指针的位置
     * 将时间复杂度由枚举三个数的n*n*n降低到n*n
     * 、
     * 如果当头值+中值+尾值恒定小于0 （中指针在头和尾遍历）说明头小，头++
     * 如果当头值+中值+尾值恒定大于0 （中指针在头和尾遍历）说明尾大，尾--
     * <p>
     * 另外一个难点 【注意：答案中不可以包含重复的三元组。】
     * 如何去重：
     * 1.方法1：顶一个一个对象R 记录三个值，重写hashCode和equals，使用set存储结果
     * 返回的时候使用stream转化为List<List<Integer>>
     * 2.方法2：如果 移动指针发现和上次的值一样 那么继续移动
     * @date 22:45 2021/9/23
     **/
    static class S1 {
        public static void main(String[] args) {
            System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        }

        public static List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums == null || nums.length < 3) {
                return res;
            }
            Arrays.sort(nums);
            int head = 0;
            for (; head < nums.length; head++) {
                if (head  > 0 && nums[head] == nums[head - 1]) {
                    continue;
                }
                int tail = nums.length - 1;
                for (int mid = head + 1; mid < nums.length; mid++) {
                    if (mid > head + 1 && nums[mid] == nums[mid - 1]) {
                        continue;
                    }
                    while (mid < tail && nums[head] + nums[mid] + nums[tail] > 0) {
                        tail--;
                    }
                    if (mid == tail) {
                        break;
                    }
                    if (nums[head] + nums[mid] + nums[tail] == 0) {
                        res.add(Arrays.asList(nums[head], nums[mid], nums[tail]));
                    }
                }

            }
            return res;
        }
    }

    static class S2{
        static class ThreeNum{
            Integer first;
            Integer second;
            Integer third;

            public ThreeNum(Integer first, Integer second, Integer third) {
                this.first = first;
                this.second = second;
                this.third = third;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof ThreeNum)) return false;
                ThreeNum threeNum = (ThreeNum) o;
                return Objects.equals(first, threeNum.first) &&
                        Objects.equals(second, threeNum.second) &&
                        Objects.equals(third, threeNum.third);
            }

            @Override
            public int hashCode() {
                return Objects.hash(first, second, third);
            }
        }
        static class TwoSum{
            Integer first;
            Integer second;
            void sort(){
                Integer firstTemp=first;
                Integer secondTemp=second;
                first=Math.min(firstTemp,secondTemp);
                second=Math.max(firstTemp,secondTemp);
            }
            public TwoSum(Integer first, Integer second) {
                this.first = first;
                this.second = second;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof TwoSum)) return false;
                TwoSum twoSum = (TwoSum) o;
                return first.equals(twoSum.first) &&
                        second.equals(twoSum.second);
            }

            @Override
            public int hashCode() {
                return Objects.hash(first, second);
            }
        }

        public static void main(String[] args) {
            System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        }
        public static List<List<Integer>> threeSum(int[] nums) {
            if (nums == null || nums.length < 3) {
                return new ArrayList<>();
            }
            HashMap<Integer, Set<TwoSum>> towSumMemory = new HashMap<>(nums.length*nums.length/2);
            for (int first = 0; first < nums.length; first++) {
                for (int second=first+1; second < nums.length; second++){
                    int tempSum=nums[second]+nums[first];
                    Set<TwoSum> twoSumSet = towSumMemory.getOrDefault(tempSum, new HashSet<>());
                    TwoSum e = new TwoSum(first, second);
                    e.sort();
                    twoSumSet.add(e);
                    towSumMemory.put(tempSum,twoSumSet);
                }
            }
            LinkedList<ThreeNum> threeNums = new LinkedList<>();
            Arrays.stream(nums).distinct().forEach(item->{
                Set<TwoSum> twoSumSet = towSumMemory.get(-item);
                if (twoSumSet!=null){
                    for (TwoSum twoSum : twoSumSet) {
                        threeNums.add(new ThreeNum(item,nums[twoSum.first],nums[twoSum.second]));
                    }
                }
            });
            return threeNums.stream().distinct()
                    .map(item -> {
                        List<Integer> temp = Arrays.asList(item.first, item.second, item.third);
                        Collections.sort(temp);
                        return temp;
                    })
                    .distinct()
                    .collect(Collectors.toList());
        }

    }
}
